package com.linzm.leetcode.primary.数组;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author zimingl
 * @Date 2022/9/15 22:21
 * @Description: leetcode 简单级别 第一页
 */

public class Page01 {

    /**
     *  1-1. 两数之和
     *  两数之和 key - 数据 value - 数组下标
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target){

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(target-nums[i])){
                return new int[]{map.get(target-nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }

    @Test
    public void twoSumTest(){
        int[] nums = new int[]{2,7,11,15};
        int target = 9;
        int[] ints = twoSum(nums, target);
        System.out.println(ints);
    }

    /* ***********************  ***********************   ***********************  ***********************  *********************** */

    /**
     * 求一个数是不是回文数
     *
     * @param x
     * @return
     */
    public static boolean isPalindrome(int x){
        /**
         * 负数
         * 0
         * 010
         */
        if (x < 0 || (x % 10 == 0 && x != 0)){
            return false;
        }
        int revertedNumber = 0;
        while (x > revertedNumber){
            revertedNumber = revertedNumber *  10 + x % 10;
            x /= 10;
        }
        // 121 revertedNumber = 12 x = 1; 91219 revertedNumber = 912 x = 91
        return x == revertedNumber || x == revertedNumber / 10;
    }

    @Test
    public void isPalindromeTest(){
        int x = 121;
        boolean flag = isPalindrome(x);
        System.out.println(flag);
    }

    /* ***********************  ***********************   ***********************  ***********************  *********************** */

    /**
     * 2-26. 删除有序数组中的重复项
     * 0022233 ——> 0232233 返回 3 并非真正地删除了元素
     * 返回数组删除后的长度
     *
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums){
        if (nums == null || nums.length == 0){
            return 0;
        }
        int p = 0;
        int q = 1;
        while (q < nums.length){
            if (nums[p] != nums[q]){
                nums[p+1] = nums[q];
                p++;
            }
            q++;
        }
        return p+1;
    }

    @Test
    public void removeDuplicatesTest(){
        int[] nums = new int[]{0,0,1,1,1,2,2,3,3,4};
        int i = removeDuplicates(nums);
        System.out.println(i);
    }

    /* ***********************  ***********************   ***********************  ***********************  *********************** */

    /**
     * 3-27. 移除元素
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }

    @Test
    public void removeElementTest(){
        int[] nums = new int[]{3,2,2,3};
        int val = 3;
        int i = removeElement(nums, val);
        System.out.println(i);
    }

    /* ***********************  ***********************   ***********************  ***********************  *********************** */

    /**
     * 4-35. 搜索插入位置
     * 折半查找法
     *
     * @param nums
     * @param target
     * @return
     */
    /*public static int searchInsert(int[] nums, int target){
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        int ans = len;
        while (left <= right){
            int mid = ( (right - left)  >> 1 ) + left;
            if (target <= nums[mid]){
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }*/
    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    @Test
    public void searchInsertTest(){
        int[] nums = new int[]{1,3,5,6};
        int val = 2;
        int i = searchInsert(nums, val);
        System.out.println(i);
    }

    /* ***********************  ***********************   ***********************  ***********************  *********************** */

    /**
     * 5-66. 加一
     * 思路
     * 当我们对数组 \textit{digits}digits 加一时，我们只需要关注 \textit{digits}digits 的末尾出现了多少个 99 即可。我们可以考虑如下的三种情况：
     * 如果 \textit{digits}digits 的末尾没有 99，例如 [1, 2, 3][1,2,3]，那么我们直接将末尾的数加一，得到 [1, 2, 4][1,2,4] 并返回；
     * 如果 \textit{digits}digits 的末尾有若干个 99，例如 [1, 2, 3, 9, 9][1,2,3,9,9]，那么我们只需要找出从末尾开始的第一个不为 99 的元素，
     * 即 33，将该元素加一，得到 [1, 2, 4, 9, 9][1,2,4,9,9]。随后将末尾的 99 全部置零，得到 [1, 2, 4, 0, 0][1,2,4,0,0] 并返回。
     * 如果 \textit{digits}digits 的所有元素都是 99，例如 [9, 9, 9, 9, 9][9,9,9,9,9]，那么答案为 [1, 0, 0, 0, 0, 0][1,0,0,0,0,0]。
     * 我们只需要构造一个长度比 \textit{digits}digits 多 11 的新数组，将首元素置为 11，其余元素置为 00 即可。
     *
     * @param digits
     * @return
     */
    public static int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] != 9) {
                ++digits[i];
                for (int j = i + 1; j < n; ++j) {
                    digits[j] = 0;
                }
                return digits;
            }
        }
        // digits 中所有的元素均为 9
        int[] ans = new int[n + 1];
        ans[0] = 1;
        return ans;
    }

    @Test
    public void plusOneTest(){
        int[] digits = new int[]{1,2,9};
        int[] one = plusOne(digits);
        System.out.println(one);
    }

    /* ***********************  ***********************   ***********************  ***********************  *********************** */

    /**
     * 6-88. 合并两个有序数组
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        /*for (int i = 0; i < n; ++i){
            nums1[m+i] = nums2[i];
        }
        Arrays.sort(nums1);*/

        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }

    @Test
    public void mergeTest(){
        int[] nums1 = new int[]{1,2,3,0,0,0};
        int[] nums2 = new int[]{2,5,6};
        merge(nums1, nums2.length + nums1.length, nums1, nums1.length);
    }

}
